package com.wushijia.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author Administrator
 * @date 2021-06-15 13:49
 */
public class QuickSort {

  public static void main(String[] args) {

    int[] arr = {4, 1, 6, 9, 10, 22, 1, 7, 8, 100};
    sort(arr, 0, arr.length - 1);
  }

  private static void sort(int[] arr, int left, int right) {
    if (left > right) {
      return;
    }

    int temp = arr[left];//temp中存的就是基准数
    int l = left;
    int r = right;
    while (l != r) {
      //顺序很重要，要先从右往左找
      while (arr[r] >= temp && l < r) {
        r--;
      }
      //再从左往右找
      while (arr[l] <= temp && l < r) {
        l++;
      }
      if (l < r) {
        swap(arr, l, r);
      }
    }
    //最终将基准数归位
    swap(arr, left, l);
    System.out.println(Arrays.toString(arr));
    sort(arr, left, l - 1);
    sort(arr, r + 1, right);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
